//搜索插入位置   力扣35
//二分查找  target只有一个的情况
//总结：
//左闭右开: 结束条件：两指针重合，若找不到，则两指针位于刚好大于targe的位置（升序）
//左开右闭：结束条件：两指针重合，若找不到，则两指针位于刚好小于targe的位置（升序）
//左闭右闭：结束条件：两指针刚好错开，若找不到，target处于两指针指向位置的值之间，left在右
//左开又开：结束条件：两指针刚好相邻，若找不到，target处于两指针指向位置的值之间，left在左
//左闭右开
class Solution {
public:
	int searchInsert(vector<int>& nums, int target) {
		int left = 0;
		int right = nums.size();
		while(left < right)
		{
			int mid = left + (right - left)/2;
			if(nums[mid] < target)  left = mid+1;
			else if(nums[mid] > target) right = mid;
			else return mid;
		}
		return right;
		//或return left
	}
};

//左开右闭
class Solution {
public:
	int searchInsert(vector<int>& nums, int target) {
		int left = -1;
		int right = nums.size()-1;
		while(left < right)
		{
			int mid = left + (right - left) / 2 + 1;
			if(nums[mid] < target) left = mid;
			else if(nums[mid] > target) right = mid - 1;
			else return mid;
		}
		//或return left + 1;
		return right + 1;
	}
};

//左闭右闭
class Solution {
public:
	int searchInsert(vector<int>& nums, int target) {
		int left = 0;
		int right = nums.size() - 1;
		while(left <= right)
		{
			int mid = left + (right - left) / 2;
			if(nums[mid] < target) left = mid + 1;
			else if(nums[mid] > target) right = mid - 1;
			else return mid;
		}
		return left;
		//或 return right + 1;
	}
};

//左开右开
class Solution {
public:
	int searchInsert(vector<int>& nums, int target) {
		int left = -1;
		int right = nums.size();
		while(left + 1 != right)
		{
			int mid = left+ (right - left) / 2;
			if(nums[mid] < target) left = mid;
			else if(nums[mid] > target) right = mid;
			else return mid;
		}
		return right ;
		//或 return left + 1;
		
	}
};
